\begin{savequote}[8cm]
What I cannot create, I do not understand.
\qauthor{Richard Feynman}
\end{savequote}

\chapter{Link prediction in location-based services}
\chaptermark{Link prediction}
\label{ch:prediction}

Online social services greatly benefit from recommending new friends to their
users, since as users add more and more friends their engagement with the
service increases.  Hence, link prediction systems have been widely deployed to
find which users should be recommended.
%
%An inherent
%characteristic of the resulting social graphs is that they may have millions of
%nodes, but, at the same time, they are often quite sparse, with low density of
%links among these nodes.  As a result, 
However, the prediction space faced by these systems is huge and highly imbalanced: given a user,
the overwhelming majority of other users are not likely to be suitable friend
recommendations. Real recommendation systems merely focus on finding
friends in the 2-hop social neighbourhood, i.e.,  friends-of-friends of a
user. For instance, a popular Facebook feature is ``People You May Know'':
launched in 2008, it suggests friends-of-friends that are likely to be
suitable for new social connections~\cite{Rat08:friends}.  As
this example suggests, extending prediction efforts to the 3-hop
neighbourhood, or even further, may not be worth the effort.
%likely result in an exponentially larger
%set of increasingly less likely prediction candidates. 

The predominance of new links between users sharing at least a common friend was
also confirmed in Chapter~\ref{ch:model}:  a large fraction of all new
connections arising in online social networks tend to arise between users
exactly two hops away from each other.  However, we also discussed how
geographic proximity is a factor that impacts new connections. Specifically,
ties arising between users that are several hops away seem to be
established between spatially close individuals.  In other
words, being close in space could be as important as being close in
the social graph, in order to create a new social tie.  Nevertheless,
geographic proximity alone could be a simplistic and imprecise
indicator of potential future connections, as it lacks the richness
of properties that can be exploited when considering the social
connections between two friends-of-friends. This implies that the model of
network evolution  presented in Chapter~\ref{ch:model} could offer insights
about what factors mainly drive user behaviour, but would only reproduce the
average behaviour  when directly applied to predict which individual social ties
are likely to be established. A link recommendation system should offer greater
accuracy: this requires more information about user actions and more complex
models.

In location-based social services there is an unprecedented source of
useful additional information about future connections: the places visited by
each user.  These places also offer a set of promising candidates. 
Given a certain user, data about venues and check-ins can be exploited at
first to select a subset of users as prediction candidates: these
``place-friends'' represent pairs of users that share at least one common place
among their check-ins.  Then, the same information can be exploited  to
identify the candidates that are more likely to become actual social
connections.  

By exploiting the properties of the venues visited by users it is possible to provide additional
predictive power to augment purely social approaches, considering how and where
different users check in.  In this chapter we build upon these initial
considerations with a practical goal in sight: to design a link prediction
system for new social connections that exploits data about user check-ins.


\paragraph{Chapter outline}
To investigate the practical feasibility of our proposal, we study 
longitudinal data about an online location-based service, Gowalla, with
information about friendship connections and check-ins.  In
Section~\ref{sec:placefriends} we analyse the link prediction space by
investigating how new friendship connections are created over time: we discover
that \textit{about 30\% of all new links appear among users who check in at the
  same places}.  Thus, these ``place-friends'' represent disconnected users that
  can become direct connections.

Hence, we argue that effective link prediction on location-based services can
greatly benefit from focussing only on the friends-of-friends and on the
place-friends of a user.  
%This design choice makes the prediction space about 15
%times smaller than the entire set of candidates and, yet, it covers about 66\%
%of new social ties. In addition, this reduced prediction set offers a better
%balance between the number of new links and its total size.  As a result,
%practical implementation of link prediction systems can become more
%efficient, since for each user only a much smaller set of potential
%friends has to be explored to compute predictions. 
%
The challenge is how to exploit the information given by the check-ins of
two users, who do not share any friends but who visit the same places, to
predict whether they will become direct connections. 
%In fact, activity and interaction revolving around physical places can result in
%social ties emerging among individuals and correlated to the properties
%of the place itself, as the sociological ``focus theory''
%suggests~\cite{Scott_81}. 
Towards this goal, in Section~\ref{sec:prediction_features} we define
prediction features which quantify how likely users are to become friends
considering the places they visit and the properties of these places. 
%Our
%prediction features are based on user check-ins and on the concept of
%``place entropy'', which discriminates venues that
%are more likely to foster social connections from those that are not.

In Section~\ref{sec:prediction_system} we present the proposed prediction
system: prediction features based on visited places, combined with other measures, are exploited
in a supervised learning framework to predict future links.  Our 
evaluation in Section~\ref{sec:prediction_evaluation} shows the effectiveness of
our design choices;  the inclusion of information about places and related user
activity offers high link prediction performance. These results open new
directions for real-world link recommendation systems on location-based social
networks, as we discuss in Section~\ref{sec:disc5}.  We present an overview of related results in
Section~\ref{sec:related5} and conclude in Section~\ref{sec:concl5}.


\section{The importance of place-friends}
\label{sec:placefriends}
In this section we analyse how new social ties are created by users of a
location-based social service. Our aim is to understand what challenges a
prediction system would face and how to overcome them.


\subsection{Snapshot properties}
We have extracted four monthly snapshots of Gowalla data from the temporal
dataset presented in Section~\ref{subsec:temporal_gowalla_data}. Each snapshot
contains the social connections between users at that time and it includes all
the check-ins made by users up until that time.

In the 4 consecutive monthly snapshots Gowalla increased its total number of
registered users from about 250 thousand to about 380 thousand, as shown in
Table~\ref{tab:placefriends_crawling_properties}. At each snapshot, about 56\%
of users are active, that is, have at least one friend or one check-in.
Each snapshot of our dataset
results in a social graph;
%containing a subset of the active users: each
%graph exhibits a large giant connected component, always
%containing more than 94\% of all the nodes. 
as the average number of friends per user grows from 8.73 to 9.24, the social
network remains sparse, making link prediction challenging because of the
scarcity of social ties. 

{\small
\begin{table}[t]
\centering
\begin{tabular}{|c||c|c|c|c|c|c|}
\hline
\emt{t} & Users & Active users & Places & Check-ins & \emt{N} & \emt{K} \\
\hline
\hline
1 & 252,020 & 148,234 &  958,823  & 7,475,401 & 109,045 & 476,409 \\
\hline                                          
2 & 291,812 & 168,925 &  1,104,771  & 9,073,157 & 124,190 & 559,901\\
\hline                                          
3 & 325,025 & 189,512 & 1,226,847  & 10,537,516 & 138,387 & 630,045\\
\hline                                          
4 & 382,750 & 216,734 &  1,421,262  & 12,846,151& 159,391 & 736,778 \\
\hline
\end{tabular}
\caption{Properties of our Gowalla dataset across the different temporal
    snapshots: total number of registered users and active users, total number
        of different places, total number of check-ins, number of nodes \emt{N}
    and edges \emt{K} in the social graph.}
\label{tab:placefriends_crawling_properties}
\end{table}
}


User check-in activity also presents a heavy-tailed
distribution: 90\% of users with check-ins have made fewer than 110 check-ins and
have visited fewer than 95 different
venues, as detailed by Figure~\ref{fig:placefriends_checkin_dist}
and Figure~\ref{fig:placefriends_place_dist}
Even though users might visit only a few places, users who visit the same places
are still more likely, on average, to become friends than would be expected, as we will
see later.

\begin{figure}[t]
  \centering
  %\subfigure[Check-ins per user]{
  \subfigure[]{
    \label{fig:placefriends_checkin_dist}
     \includegraphics[width=\doubleplotscale]{images/gowalla_dist_checkin_per_user.pdf}}
 %\subfigure[Places per user]{
  \subfigure[]{
    \label{fig:placefriends_place_dist}
      \includegraphics[width=\doubleplotscale]{images/gowalla_dist_place_per_user.pdf}}
    \caption{Complementary Cumulative Distribution Function (CCDF) of the number of
        check-ins (a) and of the number of places (b) per user for the last
            snapshot of the dataset (Month 4). The probability distributions do
            not change significantly across different snapshots.}
\end{figure}

%{\small
%\begin{table}[t]
%\centering
%\begin{tabular}{|c||c|c|c|c|}
%\hline
%\emt{t} & Users & Active users & Places & Check-ins \\
%\hline
%\hline
%1 & 252,020 & 148,234 &  958,823  & 7,475,401 \\
%\hline
%2 & 291,812 & 168,925 &  1,104,771  & 9,073,157 \\
%\hline
%3 & 325,025 & 189,512 & 1,226,847  & 10,537,516 \\
%\hline
%4 & 382,750 & 216,734 &  1,421,262  & 12,846,151 \\
%\hline
%\end{tabular}
%\caption{Properties of our Gowalla dataset across the different temporal
%    snapshots: total number of registered users and active users, total number
%        of different places, total number of check-ins.}
%\label{tab:placefriends_crawling_properties}
%\end{table}
%}

%\begin{table}[t]
%\centering
%\begin{tabular}{|c||c|c|c|c|}
%\hline
%\emt{t} & \emt{N} & \emt{K} &  \emt{G_C} & \emt{\langle k \rangle}  \\
%\hline
%\hline
%1 & 109,045 & 476,409 & 102,951 (94.4\%) & 8.73 \\
%\hline
%2 & 124,190 & 559,901 & 117,868 (94.7\%) & 9.01 \\
%\hline
%3 & 138,387 & 630,045 & 131,711 (95.1\%) & 9.10 \\
%\hline
%4 & 159,391 & 736,778 & 152,011 (95.3\%) & 9.24 \\
%\hline
%\end{tabular}
%\caption{Properties of the social graphs at each snapshot: number of nodes \emt{N} and edges \emt{K}, number
%of nodes \emt{G_C} (and their proportion) in the giant connected component and average
%node degree \emt{\langle k \rangle}.
%}
%\label{tab:placefriends_network_properties}
%\end{table}



Finally, we note that while many users might have social connections and no
check-ins, there are also many accounts with check-ins but no friends at
all. On average, \textit{only 57\% of active users have both some friends and some
check-ins, while 26\% have no friends and 17\% have no check-ins}.  This
is approximately constant across the temporal snapshots.


\subsection{Definitions and notation}
Formally, we represent each snapshot of our dataset as an undirected graph
\emt{G_t=(V_t,E_t)} for \emt{t=1,2,3,4}, where \emt{t} indicates the different
snapshots.
The set of nodes \emt{V_t=\{u_1,u_2,\ldots,u_{N_t}\}} is composed of \emt{N_t} users and
the set of edges \emt{E_t} is composed of pairs of users that are present in each
other's friend lists in snapshot \emt{t}. 
We define \emt{\Gamma_i^t} to be the set of users connected to user
\emt{u_i} in graph \emt{G_t}, so that \emt{k_i^t = |\Gamma_i^t|} is the number of friends of
\emt{u_i} in snapshot \emt{t}. In addition, there are \emt{L_t} different places \emt{M_t =
\{m_1,m_2,\ldots,m_{L_t}\}} where users have checked in and
\emt{c_{ij}^t} represents the number of check-ins that user \emt{u_i} has ever
made at place \emt{m_j} until time \emt{t}.
All the check-ins of user \emt{u_i} until time \emt{t}
can also be represented
as a vector \emt{\vec{c_i^t} = (c_{i1}^t, c_{i2}^t, \ldots c_{iL_t}^t)}. Then,
\emt{\Phi_j^t} is the set of all users who have checked in place \emt{m_j} and
\emt{\Theta_i^t} is the set of all places where user \emt{u_i} has checked in,
both until snapshot \emt{t}. Finally, \emt{A_t = \bigcup\limits_{j=1}^{L_t}
\Phi_j^t} is the set of all users with at least one
check-in at snapshot \emt{t}, while \emt{U_t = V_t \cup A_t} is the set of all
users present at snapshot \emt{t} with at least one friend or one check-in. 


\begin{figure}[ht]
\centering
\subfigure[Number of new links]{
    \label{fig:placefriends_new_links}
    \includegraphics[width=\doubleplotscale]{images/hop_new_links_7.pdf}}
\subfigure[Probability of a new link]{
    \label{fig:placefriends_new_probs}
    \includegraphics[width=\doubleplotscale]{images/hop_new_prob_7.pdf}}
    \caption{
            Number of new links appearing among pairs of nodes at different
              social distance (a) and their relative probability of appearance
              (b). Pairs of users at closer distance are both generating a
              larger fraction of all social links and more likely to generate
              them.}
    \label{fig:placefriends_imbalance_ratio}
\end{figure}

\subsection{Dividing the prediction space}
\label{subsec:prediction_sets}
Users adding friendship connections 
tend to prefer other users ``close'' to them, either
in a social sense or along other dimensions such as geographic proximity or
topic interest~\cite{LK07:prediction, AA03:friends, EPL09:friends,
  QC09:friends}.
As also discussed in Section~\ref{subsec:modeling_triangles}, many
new links appear between individuals at closer social distance to each
other, with the 2-hop neighbourhood of single nodes being the largest
source of new ties~\cite{LLC10:prediction}.  

This holds also  for the Gowalla snapshots: as shown in
Figure~\ref{fig:placefriends_new_links}, the number of new links
appearing between users who are \emt{d} hops away exponentially
decreases with \emt{d}. The likelihood that a pair of
users at network distance \emt{d} will have a link in the next snapshot of our dataset
decreases sharply with \emt{d}, as shown by
Figure~\ref{fig:placefriends_new_probs}: the probability that two users with at least
one friend in common, thus being at social distance \emt{d=2}, will become friends
is above \emt{10^{-4}}, but this value quickly drops below
\emt{10^{-5}} and to \emt{10^{-6}} at distance \emt{d=3} and \emt{d=4}, respectively. Hence, pairs
of users at larger distances give a weaker contribution to link
formation, both in terms of absolute number of new links and likelihood
of a new social tie.

Nonetheless, in a location-based social network the social dimension is not the
only one to be exploited and investigated.  Instead, in our context there is an
additional source of information about social ties: the places where users
check in. In particular, users may add a new connection not because of a shared
friend but because of a shared place.

In order to quantify how users seek and add new friends, for each snapshot and
for each user \emt{u_i} we define two sets of potential friend pairs: 

\textbf{Friends-of-friends} 
\begin{equation}
\label{eq:fof}
S_i^t = \{(u_i,u) : u \in \Big(\bigcup_{u_k \in \Gamma_i^t} \Gamma_k^t \Big) \setminus \Gamma_i^t\}
\end{equation}

\textbf{Place-friends} 
\begin{equation}
\label{eq:pof}
P_i^t = \{(u_i,u) : u \in \Big(\bigcup_{m_k \in \Theta_i^t} \Phi_k^t\Big) \setminus \Gamma_i^t\}
\end{equation}

While friends-of-friends are all those users who share at least one friend
without being directly connected, place-friends are all those users with
check-ins in at least one common place but who are not connected to each other.
These two sets may not be disjoint for a given user \emt{u_i}. Finally, we
define two sets containing all the pairs of nodes that are either
friends-of-friends or place-friends in a given snapshot: \emt{S_t =
  \bigcup\limits_{u_i} S_i^t} and \emt{P_t = \bigcup\limits_{u_i} P_i^t}.

{\small
\begin{table*}[t]
\centering
\begin{tabular}{|c||c|c|c|}
\hline
Snapshot \emt{t} & 1 & 2 & 3 \\
\hline
\emt{U_t} & 148,234 & 168,925 & 189,512 \\
\hline
\emt{E_t^{NEW}} & 43,182 (100.00\%) & 40,643 (100.00\%) & 58,238 (100.00\%) \\
\hline
\emt{S_t^{NEW}} & 24,174 (56.41\%) & 21,118 (51.96\%) & 30,581 (51.51\%) \\
\hline
\emt{P_t^{NEW}} & 13,150 (30.01\%) & 12,572 (30.93\%) & 20,107 (34.52\%) \\ 
\hline
\emt{S_t^{NEW} \cap P_t^{NEW}} & 7,677 (17.52\%) & 7,131 (17.54\%) & 10,935
(18.78\%) \\ 
\hline
\emt{S_t^{NEW} \cup P_t^{NEW}} & 30,187 (68.90\%) & 26,559 (65.35\%) & 39,753
(68.26\%) \\
\hline
\end{tabular}
\caption{Link formation: for each monthly network snapshot we report the total
    number of active users \emt{U_t}, the total number of new links appearing among
        them in the next snapshot \emt{E_t^{NEW}} and the breakdown of this quantity
        into new links appearing among friends-of-friends \emt{S_t^{NEW}} and among
        place-friends \emt{P_t^{NEW}}, including the intersection and union of these
        two latter sets. Percentages are computed with respect to the total
        number of new links.}
\label{tab:new_links}
\end{table*}
}

The monthly snapshots of our dataset make it possible to quantify how
many new social links appear within these two sets. For every network snapshot
\emt{G_t=(V_t,E_t)} we define \emt{E_t^{NEW} = E_{t+1} \cap ((U_t \times U_t) \setminus
        E_{t})} as the set of all new links appearing in the next network
snapshot \emt{t+1} between all users already present at snapshot \emt{t}.  In
Table~\ref{tab:new_links} new links appearing between temporal snapshots are
classified according to their origin: \emt{S_t^{NEW} = E_t^{NEW} \cap S_t} and
\emt{P_t^{NEW} = E_t^{NEW} \cap P_t} are, respectively, the set of new links
between friends-of-friends and the set of new links among place-friends.

About two-thirds of all new links appear within \emt{S_t \cup P_t}. In particular,
  while about 50\% of new links appear between friends-of-friends, more than
  30\% of new links are added between place-friends who check in at the
  same venues.  Finally, about 13\% of new links appear between users
  without any friends in common but who are place-friends. 


\subsection{Reducing the prediction space}
\label{subsec:imbalance}
In addition to the absolute number of new links appearing between
friends-of-friends and place-friends, it is also important to study how link
prediction feasibility can vary across these prediction spaces.
In a prediction space there are both pairs of users who will become connected
and pairs who will not: the performance of prediction approaches depends on the
total number of these potential pairs and on the relative proportion of these two
classes. Exhaustive approaches would scale with the total number of potential links,
which can become prohibitively large for real-world online social
networks with millions of users.  Also, the two classes can present
an extremely skewed distribution, with new links being greatly
outnumbered by pairs of users who will never create a social tie.
This problem is worsened by the fact that new links are actually
the occurrences of greater interest, as prediction systems obtain much more
value when predicting that two users will connect than when correctly predicting that they
will not.

\begin{figure}[t]
\centering
\subfigure[Prediction space size]{
    \label{fig:node_candidate}
\includegraphics[width=\doubleplotscale]{images/placefriends_candidates.pdf}}
\subfigure[Imbalance ratio]{
    \label{fig:node_rate}
\includegraphics[width=\doubleplotscale]{images/placefriends_success.pdf}}
\caption{Number of potential friends (a) and imbalance ratio (b) for each class of potential
new links: for social potential neighbours \emt{S_t}, for place potential
           neighbours \emt{P_t}, for their intersection, for their union, and for the
           entire set of users \emt{E_t}. Results averaged over the temporal
           snapshots.}
     \label{fig:candidates}
\end{figure}

In Figure~\ref{fig:node_candidate} we report the prediction space size for the
friends-of-friends set \emt{S_t} and the place-friends set \emt{P_t}, including also
their intersection and union, along with the size of the overall prediction
space for the entire dataset. While there are more than 11 billion pairs of
users, there are about 700 million place-friends (\emt{P_t}) and about 100 million
friends-of-friends (\emt{S_t}), with their intersection reducing the prediction
space to about 20 million entities. Thus, by focussing prediction efforts only
on place-friends or friend-of-friends the prediction space can be reduced by
about 15 times, while still covering two-thirds of all new links.  

Then, we study the \textit{imbalance ratio} of a prediction set, which is the
ratio between the total number of prediction candidates in the set  and the actual number of new links that
will appear within it.
Imbalance ratios are key indicators of link prediction systems' performance: they
express how many real instances should be considered and analysed, on average,
before a prediction can be successfully made.  Place-friends and
friends-of-friends offer lower imbalance ratios than the overall
prediction space, as shown in Figure~\ref{fig:node_rate}: hence, not
only do they offer a smaller prediction space, but the likelihood that
new links will be found is also about 20 times higher than the average.

However, discovering new ties between users who check in to the same places
appears challenging.  Not all places have the same importance for different
users and, thus, not all places are equally likely to foster new social ties
between individuals who visit them.  The key idea is then to take advantage of the
properties of a place to predict new links.


\section{Building prediction features}
\label{sec:prediction_features}
In this section we will describe how the properties of the places visited by
users can be exploited in link prediction systems. More broadly,  we will also
introduce a family of prediction features we will later adopt in our proposed
design.

\begin{figure}[t]
\centering
\includegraphics[width=\plotscale]{images/place_chk_correlation.pdf}
    \caption{Average probability that two users who have checked in a at place
        are friends, as a function of the number of check-ins in that place.}
    \label{fig:place_chk_prob}
\end{figure}

\subsection{The social properties of places}
Places can be characterised by taking into account users' check-ins: in fact,
the average probability that two users who have checked in at the same
place are friends exhibits a 
decreasing trend as the place has more check-ins, as shown in
Figure~\ref{fig:place_chk_prob}. However, there is not much difference when a place
has fewer than 100 check-ins.

A place where only a small number of users regularly check in is likely
to be a place with significant importance to them, such as private houses, gyms,
   or offices.  Conversely, a place with a similar total number of check-ins but
   where these check-ins have been made by many
users is likely to be a public place without considerable significance to
its visitors, such as touristic places, airports, train stations and so on.  

Hence, a more suitable measure of how much a venue promotes social connections
among its visitors should take into account both the number of users that check in and their number of check-ins. A feasible
combination is to exploit information theory and define an entropy-based measure
to assess the importance of a place for social link creation. \textit{Place
entropy} has been used in ecology to measure place
biodiversity~\cite{CTH11:places}: the underlying assumption is
that a uniform distribution of species in a given physical environment is
much more diverse than a skewed distribution, where only a few species are
overwhelmingly present. 
\begin{figure}[t]
\centering
\includegraphics[width=\plotscale]{images/place_ent_correlation.pdf}
    \caption{Average probability that two users who have checked in at a place
        are friends, as a function of  place entropy.}
    \label{fig:place_entropy_prob}
\end{figure}


Let \emt{C_k^P} be the total number of check-ins made by all users
at place \emt{m_k} and \emt{q_{ik} = c_{ik}/C_k^P}  the fraction of check-ins
that user \emt{u_i} has made at location \emt{m_k} with respect to the total number of
check-ins at place \emt{m_k}.  Therefore \emt{\{q_{1k},\ldots,q_{Nk}\}} is a discrete
probability distribution that describes how likely it is that a check-in at \emt{m_k}
was made by a certain user. Then, we define \emt{H_k} as the entropy of place
\emt{m_k}:
\begin{equation}
\label{eq:user_entropy}
H_k = - \sum_{u_i \in \Phi_k} q_{ik} \log q_{ik}
\end{equation}
Venues visited by several casual users are less likely to foster the creation of
social links between them.  Hence, places with higher entropy might result in
fewer social links among their visitors than venues with lower values.  This is
confirmed by Figure~\ref{fig:place_entropy_prob}: the average probability that
two users who have checked in at the same place are friends decreases as the
entropy of the place itself increases.  Place entropy seems to have strong
discriminative power; as we will see, it is a successful indicator of whether a
certain place is likely to result in social ties between its visitors.

\subsection{Feature definition}
Link prediction methods are based on numeric scores computed for pairs of users.
These values tend to capture proximity of two users across different dimensions,
with the underlying assumption that pairs of users who are similar or
close are likely to develop a social connection between them. 

We will consider \textit{social features}, which can be computed for
friends-of-friends, \textit{place features}, which can be computed for
place-friends, and \textit{global features}, which can be computed for any pair of
users, even if they do not share any friend or place. 
All features are described in Table~\ref{tab:features} and discussed in the
following paragraphs.

\begin{table}
\centering
\begin{tabular}{|l|c|}
\hline
\multicolumn{2}{|c|}{Place features} \\ 
\hline
\texttt{common\_p} &\emt{|\Theta_i \cap \Theta_j|} \\
\hline
\texttt{overlap\_p} &\emt{\frac{|\Theta_i \cap \Theta_j|}{|\Theta_i \cup \Theta_j|}} \\
\hline
\texttt{w\_common\_p} &\emt{\vec{c_i}\vec{c_j}} \\
\hline
\texttt{w\_overlap\_p} &\emt{\vec{c_i}\vec{c_j} / \sqrt{\vec{c_i}^2 \vec{c_j}^2}}\\
\hline
\texttt{aa\_ent} &\emt{\sum\limits_{m_k \in \Theta_i \cap \Theta_j} \frac{1}{H_k}}\\
\hline
\texttt{min\_ent} &\emt{\min(H_k: m_k \in \Theta_i \cap \Theta_j)}\\
\hline
\texttt{aa\_p} &\emt{\sum\limits_{m_k \in \Theta_i \cap \Theta_j} \frac{1}{\log C_k^P}}\\
\hline
\texttt{min\_p} &\emt{\min(C_k^P: m_k \in \Theta_i \cap \Theta_j)}\\
\hline
\hline
\multicolumn{2}{|c|}{Social features} \\ 
\hline
\texttt{common\_n} &\emt{|\Gamma_i \cap \Gamma_j|} \\
\hline
\texttt{overlap\_n} &\emt{\frac{|\Gamma_i \cap \Gamma_j|}{|\Gamma_i \cup \Gamma_j|}} \\
\hline
\texttt{aa\_n}  &\emt{\sum\limits_{z \in \Gamma_i \cap \Gamma_j}
\frac{1}{\log(|\Gamma_z|)}} \\
\hline
\hline
\multicolumn{2}{|c|}{Global features} \\ 
\hline
\texttt{geodist} &\emt{\text{dist}(m_{l_i},m_{l_j})} \\
\hline
\texttt{w\_geodist} &\emt{\text{dist}(m_{l_i},m_{l_j}) / c_{il_i}c_{jl_j}} \\
\hline
%\hline
%\multicolumn{2}{|c|}{User features} \\ 
%\hline
\texttt{pa} &\emt{|\Gamma_i||\Gamma_j|} \\
\hline
\texttt{pp} &\emt{|\Theta_i||\Theta_j|} \\
\hline
\end{tabular}
\caption{Formal definition of prediction features:
  \emt{\Gamma_i} is the set of users connected to user \emt{u_i}, 
  \emt{c_{ik}} is the number of check-ins made by user \emt{u_i} at place
    \emt{m_k},
 the  vector \emt{\vec{c_i}} contains all check-ins of user \emt{u_i},
 \emt{m_{l_i}} is the home location of user \emt{u_i},
\emt{\Theta_i} is the set of all places where user \emt{u_i} has checked in,
\emt{C_k^P} is the total number of user check-ins at place \emt{m_k} and 
\emt{H_k} is the entropy of place \emt{m_k}.}
\label{tab:features}
\end{table}

\subsubsection{Place features}
When two users check in to the same places they might have many chances to be in
contact with each other and, therefore, to create a new connection.
The two features \texttt{common\_p} and \texttt{overlap\_p} denote respectively
the number and the fraction of common places between two users, while
\texttt{w\_common\_p} takes into account the number of check-ins of both users and 
\texttt{w\_overlap\_p} is given by the cosine similarity of the two check-in
vectors.%\todo{cite cosine similarity}

%However, in addition to the number of shared places it is imporant to consider
%the particular places two users might share. Sharing a largely visited venue,
%such as an aiport, is less likely to foster social connections than a more
%intimate venue, such as a school or a private house.  
Then, we define two features based on the entropy of the places that two users share:
\texttt{min\_ent}, the minimum place entropy across all the shared
venues, and \texttt{aa\_ent}, the sum of the inverse of each place entropy
value, a measure inspired by the Adamic-Adar similarity
score~\cite{AA03:friends}. Similarly, we define corresponding features considering
the number of check-ins, \texttt{aa\_p} and \texttt{min\_p}: in this case the
relevance of a shared place is higher if it has only a few check-ins.

\subsubsection{Social features}
Several link prediction features are based on the assumption that two users who
share many common neighbours are more likely to create a direct connection.
Thus, given two users we define \texttt{common\_n} as their number of common
neighbours and \texttt{overlap\_n} as their Jaccard
coefficient~\cite{Sal83:ir}. In addition, \texttt{aa\_n} is their
Adamic-Adar measure based on the degrees of the shared
neighbours~\cite{AA03:friends}.

\subsubsection{Global features}
Finally, we define measures that can be adopted for any pair of users,
as they are based on their individual properties.

We define \emt{m_{l_i}} as the ``home-location'' where user \emt{u_i} has 
made the greatest number of their check-ins:
this location might not be the place where a user lives, but it gives
a reasonable estimation of the place a user seems most attached to. Then, given
two users,  we compute \texttt{geodist} as the geographic distance between their
home locations.  At the same time, \texttt{w\_geodist} is the same distance
divided by the product of the number of check-ins each user has made at their
home location.

Another method to define global features is to consider how many friends users
have added or how many places they have visited.  We define \texttt{pa} as the
preferential attachment score of two users, while  \texttt{pp}, or
\textit{place-product}, is given by the product of the numbers of places
that each user has visited.  These two features tend to capture more active
users who tend to visit many places or add many friends.

\section{System design}
\label{sec:prediction_system}
In this section we describe our link prediction framework.  Our proposal builds on two key
choices: 
\begin{itemize}
\item reducing the prediction space by focussing only on friends-of-friends and
place-friends;
\item exploiting prediction features based on the places visited by users.
\end{itemize}

We propose a \textit{supervised learning approach} to link prediction, modelling it
as a binary classification problem which adopts the prediction features
previously described.

\subsection{Prediction candidates}
Let us consider a dataset snapshot, with \emt{U_t} being the set of all users
and \emt{G_t = (V_t,E_t)} the relative social network. The link prediction
problem can be formulated as follows: given the dataset snapshot at time \emt{t} as input,
compute and return a set of pairs of users \emt{E_t^{PRED} \subset (U_t
\times U_t) \setminus E_t} who are predicted to appear as friends in
\emt{E_{t+1}}.

The entire prediction space \emt{(U_t \times U_t) \setminus E_t} contains all the
potential pairs between users that are not yet connected by a link.  Recall
that \emt{S_t} represents the friends-of-friends prediction set and \emt{P_t}
denotes the place-friends prediction set, as defined in
Section~\ref{subsec:prediction_sets}.
Exploiting the findings of our previous analysis of this prediction space in Gowalla, we
select three disjoint prediction sets:

\begin{enumerate}
\item \textbf{Social}: links appearing between users that are friends-of-friends but not
place-friends (the set \emt{S_t \setminus P_t});

\item \textbf{Place}: links appearing between users
that are place-friends but not friends-of-friends (the set \emt{P_t \setminus
    S_t});

\item \textbf{Place-social}: links appearing between users that are both
    friends-of-friends and place-friends (the set \emt{S_t \cap P_t}).
\end{enumerate}

Our choice is motivated by the fact that combining these three prediction sets
results in a set of candidates about 15 times smaller than the entire prediction
space while still allowing us to predict two-thirds of new social ties,
      as discussed in Section~\ref{subsec:imbalance}.

\subsection{Prediction algorithms}
We adopt a supervised learning approach: for every snapshot \emt{t}, we compute
features at time \emt{t} for pairs of disconnected users and we assign  a positive label to each
pair if they become connected in snapshot \emt{t+1}, and a
negative label otherwise.  Thus, training and test sets are built so that
features from a given time interval are mapped to class labels in a future time
interval.  Hence, given our 4 snapshots, we can create 3 learning sets, each one
with labels drawn from the next snapshot.  
 
Classifiers can then be trained to build models and recognise positive and
negative items from their features.  Motivated by recent
results~\cite{LLC10:prediction}, the choice of a supervised learning
formulation to address the link prediction problem stems from the heavily skewed
distribution of class labels. Unlike unsupervised methods, class distributions
are learned by supervised algorithms, allowing more effective discovery of
inter-class boundaries and hence better classification performance. 


\section{Evaluation}
\label{sec:prediction_evaluation}
We now present the experimental evaluation of our link prediction
system; this section
includes an investigation of the predictive power of each similarity
feature and then an analysis of  different
supervised classifiers that use these features. Our results show how link
prediction systems based on our proposal may be feasibly deployed in similar
services with high accuracy.

\subsection{Evaluation strategy}
For each snapshot \emt{t} and for each prediction set we sample disjoint training
and test datasets; these datasets are always sampled to maintain the original
unbalanced distribution of positive and negative items in the real data.  For every item we compute
all available prediction features; the only limitations are that in the Social
prediction set \textit{place features} are not defined and in the Place prediction set
\textit{social features} are not defined.  All our evaluation tests have been
performed with the WEKA framework, which implements 
several machine learning algorithms, using default parameters
(unless otherwise specified)~\cite{WF05:weka}.

We adopt Receiver-Operating-Characteristic (ROC) curves as the main tool to
evaluate prediction performance~\cite{PF01:roc}. ROC curves describe how the
fraction of true positives over all the positive cases changes as a function of
the fraction of false positive over all the negative cases when the decision
threshold varies.  A ROC plot is a monotonic non-decreasing plot of true
positive rate as a function of false positive rate. A random
classifier will result, on average, in the curve \emt{y=x}, while better classifiers
will result in curves closer to the upper left corner. ROC curves are particularly
able to assess classification performance for highly imbalanced datasets, as in
our case.  The area under the ROC curve (AUC) is often adopted as a
scalar measure of the overall performance.
\begin{figure*}[t]
  \centering
  \includegraphics[width=\plotscale]{images/total_roc_7_SOCIAL.pdf}
  \caption{ROC curves for individual features used as unsupervised prediction
      methods on the Social prediction set.}
        \label{fig:feature_roc_social}
\end{figure*}

\subsection{Individual features evaluation}
We first study the predictive power of each individual feature; we compute
predictive scores for every pair of disconnected users in the test set and then
we numerically rank these candidates according to their score. Given a decision
threshold, new links are predicted for all the candidates with scores higher (or
    lower, depending on the directionality) than the threshold. As we vary the
decision threshold we get true and false positives, generating a ROC curve;
these curves are presented in
Figures~\ref{fig:feature_roc_social}-~\ref{fig:feature_roc_both} for each
prediction set. 

\begin{figure*}[t]
  \centering
  \includegraphics[width=\plotscale]{images/total_roc_7_PLACE.pdf}
  \caption{ROC curves for individual features used as unsupervised prediction
      methods on the Place prediction set.}
        \label{fig:feature_roc_place}
\end{figure*}


In the Social prediction space, as shown in Figure~\ref{fig:feature_roc_social},
   the best feature is \texttt{aa\_n}.
   Interestingly, we observe how the global features \texttt{pa} and \texttt{pp}
   perform worse than a random predictor. This indicates that in the social
   neighbourhood of a given user global indicators are not as useful as measures
   based on common friends: this may be a consequence of users having no access to a
   global view of the network. Instead, global features \texttt{geodist} and
   \texttt{w\_geodist} perform better, with the former being more accurate than the
   latter. Overall,  \texttt{aa\_n}, \texttt{overlap\_n} and \texttt{geodist}
   give the best performance, with AUC values between 0.73 and 0.82.

\begin{figure*}[t]
  \centering
  \includegraphics[width=\plotscale]{images/total_roc_7_BOTH.pdf}
  \caption{ROC curves for individual features used as unsupervised prediction
      methods on the Place-social prediction set.}
        \label{fig:feature_roc_both}
\end{figure*}

In the Place prediction space, as reported in
Figure~\ref{fig:feature_roc_place}, \texttt{min\_ent}, \texttt{w\_overlap\_p}
and \texttt{min\_p} show the best results, followed by \texttt{aa\_ent} and
\texttt{aa\_p}.  Sharing places with low entropy values or with a few check-ins
seems an important indicator of potential friendship, as well as having a large
overlap of visited places.  These features achieve high AUC values between 0.87
and 0.90.  The other features perform slightly worse, with \texttt{geodist}
doing better than the others. Global features \texttt{pa} and \texttt{pp}
again show inverted performance, as in the Social case.


Finally, in the Place-social prediction space, as shown in
Figure~\ref{fig:feature_roc_both}, all
prediction features can be evaluated. Just as \texttt{aa\_n} dominates in Social
and \texttt{min\_ent} dominates in Place, they also achieve the best results in this
case, with the former having a larger AUC (0.80 against 0.76). 

In general, prediction performance is higher in the Place set, while prediction
within the other two sets achieves lower AUC values.  It seems easier to
predict links between place-friends than between friends-of-friends: this may be due
to the fact that more information is available when two users share visited
places than when they share friends.  However, the prediction space is much
larger in the Place set than in the other two sets, offering an interesting
trade-off between prediction effectiveness and search complexity.

In essence, the Social set provides good candidates for new links, given its
lower imbalance ratio, but then it is difficult to discriminate between them
because there is no other information except global features and shared friends.
 Even if the Place set has higher imbalance ratios, the properties of
the places where users check in provide useful information to discover new
friendship connections.  Finally, the Place-social set, which provides the
lowest imbalance ratio across the three sets, is still a source of good
candidates like the Social set but since more information is available with
respect to location-based user activity, prediction performance is better.

\begin{table}[t]
\centering
\begin{tabular}{|l|l|c|c|c|}
\hline
Algorithm & Set & Precision & Recall & AUC \\
\hline
\multirow{3}{*}{Model}   & S & 0.79 \emt{\pm} 0.04 & 0.28 \emt{\pm} 0.05&
\textbf{0.91 \emt{\pm} 0.02} \\
\multirow{3}{*}{trees}& P & 0.87 \emt{\pm} 0.06 & 0.34 \emt{\pm} 0.06 &
\textbf{0.93 \emt{\pm} 0.01} \\
                    & PS & 0.92  \emt{\pm} 0.03 & 0.62 \emt{\pm} 0.07&
                    \textbf{0.96 \emt{\pm} 0.01} \\
\hline
\multirow{3}{*}{Random} & S & 0.92 \emt{\pm} 0.05 & 0.39 \emt{\pm} 0.05 &
\textbf{0.91 \emt{\pm} 0.02} \\
\multirow{3}{*}{forests}& P  & 0.95 \emt{\pm} 0.04& 0.72 \emt{\pm} 0.08&
\textbf{0.94 \emt{\pm} 0.03} \\
                  & PS & 0.98 \emt{\pm} 0.04 & 0.84 \emt{\pm} 0.09 &
                  \textbf{0.95 \emt{\pm} 0.01} \\
\hline
\multirow{3}{*}{J48} & S & 0.63 \emt{\pm} 0.05 & 0.04 \emt{\pm} 0.01 & 0.62 \emt{\pm} 0.08\\
                      & P & 0.86 \emt{\pm} 0.06 & 0.34 \emt{\pm} 0.04 & 0.90 \emt{\pm} 0.04\\  
               & PS & 0.90 \emt{\pm} 0.03 & 0.64 \emt{\pm} 0.08 & 0.91 \emt{\pm} 0.02\\
\hline
\multirow{3}{*}{Na\"{i}ve} & S & 0.01 \emt{\pm} 0.00 & 0.16 \emt{\pm} 0.02 &
0.74 \emt{\pm} 0.06 \\
\multirow{3}{*}{Bayes}     & P & 0.01 \emt{\pm} 0.01 & 0.36 \emt{\pm} 0.04 &
0.92 \emt{\pm} 0.04 \\
                          & PS & 0.04 \emt{\pm} 0.01 & 0.22 \emt{\pm} 0.05 &
                          0.82 \emt{\pm} 0.06\\
%\hline
%\multirow{3}{*}{Adaptive}& S & 0.00 & 0.00 & 0.81 \\
%\multirow{3}{*}{boosting} & P & 0.00 & 0.00 & 0.94 \\
%                   & PS & 0.00 & 0.00 & 0.86 \\
%\hline
%\multirow{3}{*}{Logistic} & S & 0.11 & 0.01 & 0.81 \\
%\multirow{3}{*}{regression}& P & 0.02 & 0.00 & 0.94 \\
%                    & PS & 0.04 & 0.00 & 0.84 \\
%\hline
%\multirow{3}{*}{OneR} & S & 0.90 & 0.08 & 0.56 \\ 
%                       & P & 0.91 & 0.21 & 0.60 \\ 
%                & PS & 0.92 & 0.44 & 0.70 \\
\hline
\end{tabular}
\caption{Precision and recall for the positive items, and overall AUC for different
    supervised classifiers on the three different prediction sets Social
        (S), Place (P) and Place-social (PS). Results obtained through 10-fold
        cross validation and averaged over 20 different random training sets from
        snapshot \emt{t=1}.}
\label{tab:algorithms}
\end{table}

\subsection{Combining features: supervised learning}
We assess whether our prediction features can be  combined to characterise a
model of link formation across the three prediction sets. Our aim is to achieve
at least the same predictive power as the best individual features with a
supervised algorithm. We compare the performance of the following
classifiers:  
%adaptive boosting with decision stumps, 
    J48 decision trees (equivalent to decision trees built using the C4.5
        algorithm, based on information entropy~\cite{Qui93:j48}), Na\"{i}ve Bayes~\cite{Zha04:bayes},
    model trees (decision trees with linear
    regression models on the leaves~\cite{FWI98:modeltrees}),
    %multinomial logistic regression~\cite{lecessie1992},
    and random forests (10 decision trees, 4 random features
        each)~\cite{Bre01:randomforest}.
    We run 10-fold cross validation over 20 different training set sampled over
    each prediction dataset and we consider the AUC value as an overall
    performance metric~\cite{Qui93:j48}.  In addition, we also consider two
    additional metrics computed over positive items: the average \textit{precision}, that
    is, the fraction of positive predictions that are correct, and the
    average \textit{recall}, that is, the fraction of real links that are correctly predicted.

We present our results in Table~\ref{tab:algorithms}. There is 
variability across different classifiers: the best performance in terms of AUC
is given by random forests and model trees, which are the only two methods that
outperform individual features across the three prediction sets (the only
exception being random forests underperforming on the Place set).
Random forests present higher values of precision and recall than model
trees.  

\begin{figure}[t]
\centering
    \subfigure[Model trees]{
        \label{fig:roc_regression}
        \includegraphics[width=\doubleplotscale]{images/auc_bars_regression.pdf}}
    \subfigure[Random forests]{
        \label{fig:roc_randomforest}
        \includegraphics[width=\doubleplotscale]{images/auc_bars_randomforest.pdf}}
    \caption{Prediction performance in terms of AUC of model
        trees (a) and random forests (b) on the three separate Social, Place
            and Place-social prediction sets, in each temporal snapshot.
            Results averaged over 20 random datasets.}
        \label{fig:auc_bars}
\end{figure}

As random forests and model trees outperform the other methods, we choose these
two classifiers for the next part of this evaluation, where we consider
prediction performance across consecutive temporal snapshots of Gowalla.  In
this case, for every snapshot and for each prediction set we sample disjoint
training and test sets of equal size and we compute predictions, averaging
results over 20 randomly sampled datasets.  As seen in
Figure~\ref{fig:auc_bars}, model trees achieve better AUC values for the
three prediction sets and across temporal snapshots. Overall, the two algorithms
have lower performance in the Social prediction set, with AUC values between
0.88 and 0.91, whereas Place and Place-social present higher values.  Model
trees offer slightly better performance than random forests: in particular, the
latter algorithm performs worse than individual features on the Place prediction set. A
potential explanation for this behaviour is that random forests tend to perform
poorly when faced with a large heterogeneous set of features, since randomly
chosen features are more likely to include less relevant
information~\cite{GGC08:decisiontree}. This may be the case for the Place set,
while this is not the case for the Social set, where there are fewer
features, nor for the Place-social set, where there are more features but
their prediction performance is more homogeneous.  However, investigating
the precision-recall trade-off offers a different insight into the prediction
performance. Given the same level of precision, random forests consistently
achieve higher values of recall than model trees, as described in
Figure~\ref{fig:precall}.  In summary, our prediction framework offers high
effectiveness with both methods, since they are able to leverage the information
contained in our prediction features.

Finally, to understand the extent to which different feature classes 
contribute to prediction performance, we focus only on the Place-social
prediction set, where all features are used to build the prediction model, and
we test the prediction performance that can be achieved by using only one feature
class, as compared to the full model.  As described in
Table~\ref{tab:auc_compare}, social features alone show the worst
performance, while both place and global features achieve AUC values closer to
the full model. Hence, these two latter classes are mainly contributing to the
overall performance, as they exploit information about place check-ins (Place
        features) and geographic distance between users (Global features).
Again, this provides evidence that including data coming from
location-based activity in the prediction model leads to better performance than
purely social-based methods.

\begin{figure}[t]
\centering
    \subfigure[Model trees]{
        \label{fig:precall_regression} 
        \includegraphics[width=\doubleplotscale]{images/test_precall_5_regression.pdf}}
    \subfigure[Random forests]{
        \label{fig:precall_forests}
        \includegraphics[width=\doubleplotscale]{images/test_precall_5_randomforest.pdf}}
    \caption{Precision-recall curves for model trees (a) and random forests (b)
        obtained for the three separate prediction sets, averaged across the
            three temporal snapshots. }
        \label{fig:precall}
\end{figure}


\section{Discussion and implications}
\label{sec:disc5}
Our results arise from two main important design choices: focussing link prediction only
on a reduced set of candidate pairs of users and exploiting location-based
user activity to define successful prediction features. These two simple ideas
are able to improve overall performance of link prediction systems; as a
consequence, real-world systems can be deployed, making use of predicted links
to suggest friends to users and engage them more with the service.  In addition,
   recommending to a user others who check in to the same places may be more
   important in location-based services, since users can directly interact with
   them when checking in to these places.

%In practical
%implementations, friends-of-friends and place-friends of a user can be
%analysed and our prediction features can be applied to compute the best
%candidates to be suggested.

%Furthermore, we have shown how properties of the locations visited by the users
%can give valuable insight to profile user interactions. In particular, we have
%described entropy-based measure that are able to discern if users are more
%active and, therefore, more likely to create friendship connections. In
%addition, users with higher entropy may be more appealing for advertisement
%campaign or for viral marketing strategies, since they might be perceived as the
%most influential individuals within the service. However, further studies are
%needed to explore this conjecture.
%
%We have also shown how places with higher entropy are likely to exhibit chance
%encounters between strangers, while lower entropy places are more likely to be
%visited by friends. This opens new possibility to interpret and understand how
%different places how used: it might be possible to devise automatic strategies
%that discriminate public from private places just by analysing user check-ins,
%thus improving noise in user-reported data.

Our framework enables the prediction of new social ties even for users
who do not yet have any friendship connection, provided that they visit and
check in at places.  Standard link prediction methods based on social features
are of no use in this scenario, since it is impossible to compute prediction
features for these isolated users~\cite{LCB10:coldstart}.
%Instead, our prediction features based on place activity can be exploited to predict the links they are going to establish.  
In some sense, this is a scenario that represents new users of the
service: they have signed up, they have checked in at some places but they are
not engaging with other users.  Thus, predicting their future links might be
extremely important to make them more active participants.
%
%We note that, on average, about 5\% of new links appear among pair of users
%who check-in at the same places but where one of the two has no friends at all.
%This proportion falls within our Place prediction set, but we want to understand
%what performance we achieve on these candidates separately. Thus, we create
%training and test datasets which
%contain those subset of candidates in Place set where at least one of the two
%users has no friends at all. By adopting place features, along with global 
%features, we achieve AUC values above 0.95
%and precision levels of about 0.90. 
%These users are often not very active: they have no friends and often few check-ins
%and, thus, they may tend to add as friends those users who are present at the
%few places they check-in. Our prediction features are able to discern which
%candidates are more promising: this result opens new possibility for link
%prediction and suggestion systems for initial users of location-based services, unraveling a
%great potential to engage them and avoid them stopping using the service because
%of lack of interest.
%One final observation is that this work focusses on a service where social links
%are added through means which are independent from the system itself, since
%there was no recommendation system deployed on Gowalla during our data
%collection.  
%Potentially, our proposal to exploit location-based
%activity to predict new friends could result in improving prediction performance
%even further by accessing additional information, such as fine-grained temporal
%information of user activity or direct interaction among users. For instance,
%users that check-in at the same place and \textit{at the same time} can be much
%more likely to become friends~\cite{CBC10:inferring}.
\begin{table}[t]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
Classifier & Full model & Social  & Place & Global \\
\hline
Model trees & 0.953 \emt{\pm}  0.015 & 0.907 \emt{\pm} 0.021 & 0.927 \emt{\pm} 0.011 & 0.925  \emt{\pm} 0.012\\
\hline
Random forests & 0.932 \emt{\pm} 0.013 & 0.881 \emt{\pm} 0.019& 0.923 \emt{\pm} 0.009  & 0.928  \emt{\pm} 0.012 \\
\hline
\end{tabular}
\caption{Average AUC and standard deviation for model trees and random forests
  for the Place-social prediction set when the full set of prediction features
    is used, and when only a single set of prediction features is used. Results
      averaged over the three snapshots and over 20 different random training
      and test sets for each snapshot.}
\label{tab:auc_compare}
\end{table}


\section{Related work}
\label{sec:related5}
The link prediction problem in social networks has been under scrutiny for many
years. The seminal work by Liben-Nowell and Kleinberg addresses the problem from
an algorithmic point of view, investigating how different proximity features can
be exploited to predict the occurrence of new ties in a social
network~\cite{LK07:prediction}. They adopt an unsupervised approach, where
scores are computed for all potential candidates and then ranked to obtain the
most likely predictions. 

More recently, researchers have advocated supervised
approaches to link prediction, given the possibility of modelling the task
as a binary classification problem. In particular, Lichtenwalter et al. have
presented a detailed analysis of challenges in link prediction systems,
discussing imbalance problems and proposing to treat prediction separately for
different classes of potential friends~\cite{LLC10:prediction}.  While we also
adopt a supervised approach, we additionally consider how link
prediction can be performed when information not arising from social
ties is available. 

A related approach to finding online social ties between mobile users has been
presented by Cranshaw et al.~\cite{CTH11:places}: they track a small number of
mobile users in the physical world to discover their connections on online
social networks. While also focussing on information-based measures, our
approach considers a much larger set of users and studies their activity on a
location-based service.  Eagle et al. have considered how interactions between
people over mobile phones can accurately predict relations between
them~\cite{EPL09:friends}.  Conversely, 
  we consider neither direct interaction nor communication between users to
  predict social links.

Another work by Crandall et al.~\cite{CBC10:inferring} shows how temporal and
spatial co-occurrences between people help to infer social ties among them; while
their main goal is to  put forward a generative model that explains empirical
data, our study has a different aim, that is, designing a link prediction system
to be used on real-world location-based services.  Furthermore, our work deals
with a different type of data: since we exploit check-ins at well-defined
venues, we can infer that two individuals visited exactly the same place without
dealing with generic geographic coordinates. As a consequence, our prediction
system achieves higher precision while being more practical for a real-world
deployment.

\section{Summary}
\label{sec:concl5}
In Section~\ref{sec:lbsns} we discussed how the availability of
online location-sharing services provides a window on the spatial properties of
social behaviour; in addition, and maybe with more important consequences, such
services also highlight the rising importance that physical places have for the
Web. As users can seamlessly generate and consume information related to the
venues they visit, they leave behind them a trail of digital traces that offers
unprecedented opportunities to understand and model their behaviour and to build
and design related systems.

Then, in Chapter~\ref{ch:model} we found that geographic proximity appears to be a
driving factor when users establish new social connections; in particular, when
users do not belong to the same social communities, spatial proximity can bring
together otherwise disconnected individuals. The challenge appeared to be how to
accurately build upon spatial proximity to offer precise predictions about
potential future social ties. In this chapter we have shown  how the
properties of the places that people visit can solve this problem, accurately
predicting when two users that visit the same places will become connected.

%Specifically, we have focussed on one important application which largely
%benefits from additional information about where users are located and go: the
%prediction of new social ties.  We have described and evaluated a link
%prediction model based on properties of the places visited by users of a
%location-based social network.  
%We have presented a study about the creation of
%new social links between users of a large real-world service, Gowalla: we have
%found that about 30\% of new links are added among individuals that do share
%visited places. We have denoted this potential relationships as place-friends,
%discussing their importance to provide promising candidates for link
%prediction. Hence, we have discussed that the link prediction space can
%be reduced about 15 times by focussing on place-friends and
%friends-of-friends only, while still discovering about 66\% of all new
%links.  
%Then, we have described how the properties of the venues visited by users can be
%used to define prediction features with high predictive power. Building on these
%findings, we have shown that real link prediction systems can achieve high
%precision in a prediction space smaller than exhaustive approaches.

Specifically, we have focussed on one important application that largely
benefits from additional information about where users go: the
prediction of new social ties.  We have described and evaluated a link
prediction model based on properties of the places visited by users of a
location-based social network.  
By focussing only on friends-of-friends and place-friends, and by adopting
prediction features based both on social properties and on the features of the
places visited by  users, link prediction systems can achieve high
precision in a smaller prediction space than with exhaustive approaches.

In this chapter we have seen one practical application scenario where the
spatial properties of online social services can be successfully exploited. In
the next chapter we will present another practical case where such spatial
characteristics offer tangible benefit: understanding where requests for online
content arise on a planetary scale, to optimise the delivery of such content
items.
